package _01_第一季.树04.Tree02;

import java.util.Comparator;

public class RBTree<E> extends BBST<E>{
    private static final boolean RED = false;
    private static final boolean BLACK = true;

    public RBTree(){
        this(null);
    }

    public RBTree(Comparator<E> comparator){
        super(comparator);
    }

    private static class RBNode<E> extends Node<E>{
        boolean color = RED;
        public RBNode(){
            this(null,null);
        }
        public RBNode(E element,Node<E> parent){
            super(element, parent);
        }
        @Override
        public String toString() {
            String str = "";
            if(color == RED){
                str = "R_";
            }
            return str+element.toString();
        }
    }

    @Override
    protected void afterAdd(Node<E> node) {
        Node<E> parent = node.parent;

        if(parent == null){
            black(node);
            return;
        }

        //添加节点的父节点是黑色
        if(isBlack(parent)) return;

        Node<E> uncle = parent.sibling();
        Node<E> grand = parent.parent;
        if(isRED(uncle)){
            black(parent);
            black(uncle);
            afterAdd(red(grand));
            return;
        }

        if(parent.isLeftChild()){
            red(grand);
            if(node.isLeftChild()){ //LL
                black(parent);
            }else{ //LR
                black(node);
                rotateLeft(parent);
            }
            rotateRight(grand);
        }else{
            red(grand);
            if(node.isLeftChild()){
                black(node);
                rotateRight(parent);
            }else{ //RR
                black(parent);
            }
            rotateLeft(grand);
        }
    }

    /**
     * 传过来的是待删除的节点或者替代的子节点
     * @param node
     */
    @Override
    protected void afterRemove(Node<E> node) {
        //删除的是红色节点或者删除黑色节点且用以替代的节点是红色
        if(isRED(node)){
            black(node);
            return;
        }

        Node<E> parent = node.parent;
        if(parent == null) return;

        //删除黑色叶子节点
        //需要找到兄弟节点，但是兄弟节点在之前的删除逻辑中父节点的那根线已经断了，无法通过node.sibling()找到兄弟节点
        //逆向思维 判断被删除的节点在左还是右
        boolean left = parent.left == null || node.isLeftChild();
        Node<E> sibling = left ? parent.right : parent.left;
        if(left){ //被删除的节点在左边，兄弟节点在右边
            if(isRED(sibling)){
                black(sibling);
                red(parent);
                rotateLeft(parent);
                sibling = parent.right;
            }

            //兄弟节点没有红色子节点可以借
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                boolean parentBlack = isBlack(parent);
                red(sibling);
                black(parent);
                if(parentBlack){
                    afterRemove(parent);
                }
            }else{
                if(isBlack(sibling.right)){
                    rotateRight(sibling);
                    sibling = parent.right;
                }
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateLeft(parent);
            }
        }else{ //被删除的节点在右边，兄弟节点在左边
            if(isRED(sibling)){
                black(sibling);
                red(parent);
                rotateRight(parent);
                sibling = parent.left;
            }

            //兄弟节点没有红色子节点可以借
            if(isBlack(sibling.left) && isBlack(sibling.right)){
                boolean parentBlack = isBlack(parent);
                black(parent);
                red(sibling);
                if(parentBlack){
                    afterRemove(parent);
                }
            }else{
                if(isBlack(sibling.left)){
                    rotateLeft(sibling);
                    sibling = parent.left;
                }
                color(sibling,colorOf(parent));
                black(sibling.left);
                black(parent);
                rotateRight(parent);
            }
        }
    }

    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new RBNode<>(element,parent);
    }

    private Node<E> color(Node<E> node,boolean color){
        if(node == null) return null;
       ((RBNode<E>)node).color = color;
        return node;
    }

    private Node<E> black(Node<E> node){
        return color(node,BLACK);
    }

    private Node<E> red(Node<E> node){
        return color(node,RED);
    }

    private boolean colorOf(Node<E> node){
        return node == null ? BLACK : ((RBNode) node).color;
    }

    private boolean isBlack(Node<E> node){
        return colorOf(node) == BLACK;
    }

    private boolean isRED(Node<E> node){
        return colorOf(node) == RED;
    }
}
